package leetcode.method.dynamic_programming;

/**
 * 乘法太多浪费计算时间
 */
public class Program62UniquePath1 {

    public Program62UniquePath1() {
    }

    public int uniquePaths(int m, int n) {
        if (m < 0 || n < 0) {
            return 0;
        }
        if (m == 1 || n == 1) {
            return 1;
        }
        int[][] coun = new int[m][n];

        coun[0][0] = 1;
        for (int i = 1; i < n; i++) {
            coun[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            coun[i][0] = 1;
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                coun[i][j] = coun[i][j -1] + coun[i - 1][j];
            }
        }
        return coun[m - 1][n - 1];
    }

    public static void main(String[] args) {
        Program62UniquePath1 myStack = new Program62UniquePath1();
        System.out.println(myStack.uniquePaths(3,7));
        System.out.println(myStack.uniquePaths(3,2));
        System.out.println(myStack.uniquePaths(7,3));
        System.out.println(myStack.uniquePaths(3,3));
    }
}
